package Sort.sort2020_2;

/**
 * 快速排序
 * 从小到大
 * @author: leiwenkang
 * @date: 2020/5/23
 * @time: 18:17
 */
public class QuickSort {

//    public static void main(String[] args) {
//        int[] array = {3,8,4,6,7,2,5,9,1};
//        sort(array);
//        for (int i = 0; i < array.length; i++){
//            System.out.print(array[i]);
//            System.out.print(" ");
//        }
//    }

    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int pos = partition(array, low, high);

        quickSort(array, low, pos - 1);
        quickSort(array, pos + 1, high);
    }

    private static int partition(int[] array, int low, int high) {
        int val = array[low];
        while (low < high) {
            while (low < high && array[high] >= val) {
                high--;
            }
            array[low] = array[high];

            while (low < high && array[low] <= val) {
                low++;
            }
            array[high] = array[low];
        }
        array[high] = val;
        return high;
    }

    public static void main(String[] args) {
        System.out.println("Hello World!");
        int[] array = {3,8,4,6,7,2,5,9,1};
        int length = array.length;
        int left = 0;
        int right = length-1;
        qulckSort(array,left,right);
        for (int i = 0; i < array.length; i++) {
                        System.out.print(array[i]);
                        System.out.print(" ");
        }

    }

    public static void qulckSort(int[] nums,int left,int right){
        if(left>=right){
            return ;
        }

        int i = left,j = right;
        int value = nums[i];
        while(i<j){
            while(i<j && nums[j]>value){
                j--;
            }
            nums[i] = nums[j];
            while(i<j && nums[i]<value){
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = value;
        qulckSort(nums,left,i);
        qulckSort(nums,i+1,right);
    }
}
